#include <iostream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include    <cstdlib>
#include    <ctime>
#include    <sys/timeb.h>



using namespace std;

struct Edge{
	int id;
	int w1;
	int w2;
	int u;
	int v;
};
struct Result{
	int w1;
	int w2;
	int k;
	list<int> C;
};
struct Graph{
	int nodes;
	vector<Edge> adjacencyMatrix;
	list<int> nodesOrder;
};

bool buscarNuevo(list<int>&,Graph*, int, int , int&, int,int&, int& );
void busquedaLocal(Result* ,Graph*,int , int ,int ,int );
void busquedaGrasp(Graph*,int, vector< vector<int> > ,int,int ,int );
void removeEdge(Graph* ,int,int ,int);
void putEdge(Graph*,int ,int ,Edge*,int);
void printGraph(Graph*);
void printAdjacencyMatrix(Graph *);
bool existNode(Graph*,int);
Edge* getEdge(Graph*,int,int,int);
Edge* createEdge(int,int,int);
void initGraph(Graph*,int);
bool compareEdgesByW2(Edge*,Edge*);
bool compareEdgesByW1(Edge*,Edge*);
Result* CalcularCamino(Graph*,Graph*, list<Edge*>*,int,int,int,int,int);
Result* CalcularCaminoDijkstra(Graph*,Graph*, list<Edge*>*,int,int,int,int,int);
Result* CalcularCaminoDijkstraRandom(Graph*,Graph*, list<Edge*>*,int,int,int,int,int);
Result* CalcularCaminoDijkstraGreedy(Graph*,Graph*, list<Edge*>*,int,int,int,int,int);